package com.leetcode.根据算法进行分类.动态规划算法相关;

/**
 * @author: ZhouBert
 * @date: 2021/3/23
 * @description: 练习：编辑距离 II
 * https://leetcode-cn.com/leetbook/read/high-frequency-algorithm-exercise/omxcgt/
 * 给你两个单词 s 和 t，请你计算出将 s 转换成 t 所使用的最少操作数。
 * <p>
 * 你可以对一个单词进行如下两种操作：
 * <p>
 * 删除一个字符
 * 替换一个字符
 * 注意：
 * <p>
 * 不允许插入操作
 * 题目保证有解
 * <p>
 * 示例：
 * 输入：s = "abcdefg", t = "abdde"
 * 输出：3
 * <p>
 * 提示：
 * 1 <= len(s), len(t) <= 200
 */
public class B_练_编辑距离_II {

	static B_练_编辑距离_II action = new B_练_编辑距离_II();

	public static void main(String[] args) {
		test1();
	}

	static void test1() {
		String s = "abcdefg";
		String t = "abdde";
		int res = action.edit_distance(s, t);
		System.out.println("res = " + res);
	}

	/**
	 * 做一个dp[i][j] 用来表示：t[j] 转 s[i] 时需要的最少次数
	 *
	 * @param s
	 * @param t
	 * @return
	 */
	public int edit_distance(String s, String t) {
		//t-行 s-列
		char[] charsS = s.toCharArray();
		char[] charsT = t.toCharArray();
		int lenS = charsS.length;
		int lenT = charsT.length;
		int[][] dp = new int[lenT + 1][lenS + 1];
		for (int i = 1; i <= lenS; i++) {
			dp[0][i] = dp[0][i - 1] + 1;
		}
		for (int i = 1; i <= lenT; i++) {
			char cs = charsS[i - 1];
			char ct = charsT[i - 1];
			dp[i][i] = cs == ct ? dp[i - 1][i - 1] : dp[i - 1][i - 1] + 1;
			for (int j = i + 1; j <= lenS; j++) {
				cs = charsS[j - 1];
				dp[i][j] = dp[i - 1][j - 1];
				if (cs == ct) {

				} else {
//					dp[i][j] = dp[i][j - 1] + 1;
					dp[i][j] = Math.min(dp[i][j - 1], dp[i][j]) + 1;
				}
			}
		}
		return dp[lenT][lenS];
	}

}
